/**
 * 经典三角形地图，每次能往下走到相邻两格
 * 求从顶到底的最小代价，底部终点可能是N个
 * 
 */
class Solution {

using vi = vector<int>;

vector<vi> D;
int N, M;
vector<vi> *Pdata;
int None;


public:
    int minimumTotal(vector<vector<int>>& triangle) {
        N = triangle.size();
        M = triangle.back().size();
        Pdata = &triangle;
        None = -12345678;

        D.assign(N, vi(M, None));
        return dp(0, 0);
    }

    int dp(int r, int c){
        if(None != D[r][c]) return D[r][c];
        if(r == N - 1) return D[r][c] = (*Pdata)[r][c];

        int ans = dp(r + 1, c);
        ans = min(ans, dp(r + 1, c + 1));
        return D[r][c] = ans + (*Pdata)[r][c];
    }
};